package Demo1;

//找出数组0~n间缺少的元素
class Solution {
    /*
    解题思路：
    直接将数组中所有元素之和sum，然后求出1~N的前N项和-sum即可
    时间复杂度O(N)，空间复杂度:O(1)
    缺陷：如果数组中元素比较多，相加完成之后容易溢出
     */
    public int missingNumber1(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; ++i){
            sum += nums[i];
        }
        return ((1+nums.length)*nums.length)/2 - sum;
    }

    /*
        解题思路：
          采用异或的方式解决，因为两个相同的数字异或的结果是0
          因此：将0~N之间的数字，与数组中的每个数字异或，
                最终的结果就是丢失的数字
     */
    public int missingNumber2(int[] nums) {
        int data = 0;
        for(int i = 0; i < nums.length; ++i){
            data ^= nums[i];
            data ^= i;
        }
        data ^= nums.length;
        return data;
    }

    /*
        解题思路：
        将1~N之间的数组相加，然后减去nums数组中的每个数字
     */
    public int missingNumber(int[] nums) {
        int data = nums.length;
        for(int i = 0; i < nums.length; ++i){
            data = data - nums[i] + i;
        }
        return data;
    }
}